// 文件名：priority_queue_topk_stream.cpp
// 目的：从数据流中在线维护“前 K 大”元素，使用最小堆（小顶堆）实现。
// 思路：
//   - 维护一个容量为 k 的最小堆：堆顶是当前 Top-K 中最小的那个；
//   - 遍历数据流：
//       * 若堆未满，直接 push；
//       * 若堆已满且新值 > 堆顶，则弹出堆顶并推入新值；
//   - 结束后堆内即为 Top-K 元素集合（未排序）。
// 复杂度：
//   - 时间：O(N log k)，N 为流长度；空间：O(k)。
// 注意：
//   - 返回的 result 是从小顶堆依次弹出得到的升序（相对堆序）序列，若需降序展示，可在返回前逆序或显式排序。

#include <functional>
#include <iostream>
#include <queue>
#include <vector>

std::vector<int> topK(const std::vector<int>& stream, std::size_t k) {
    if (k == 0) return {};

    // 小顶堆：堆顶最小，便于踢出 Top-K 中最小者
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

    for (int value : stream) {
        if (minHeap.size() < k) {
            minHeap.push(value);
        } else if (value > minHeap.top()) {
            minHeap.pop();
            minHeap.push(value);
        }
    }

    // 将堆内容导出（注意：从小到大弹出）
    std::vector<int> result;
    result.reserve(minHeap.size());
    while (!minHeap.empty()) {
        result.push_back(minHeap.top());
        minHeap.pop();
    }
    return result; // 注意：结果未按降序排序，可逆序或排序。
}

int main() {
    std::vector<int> data = {5, 1, 9, 3, 14, 2, 8, 7, 6};
    auto top = topK(data, 4);

    std::cout << "Top 4 elements (ascending heap order): ";
    for (int v : top) {
        std::cout << v << ' ';
    }
    std::cout << '\n';

    return 0;
}